import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-02-05
 * Time: 22:14
 */
public class Solution {
//     递归(回溯)
//     选择当前元素和不选择当前元素
//     注意先选再不选, 因为这样你就把当前元素给删了
//     不会影响后面的添加
//     并且每个子集都不同, 所以往 lists 里面添加时要重新 new 一个
//     不然会使 所有的子集都一样
    List<List<Integer>> lists=new ArrayList<>();
    List<Integer> list=new ArrayList<>();
    public int length;
    public int[] arr;
    public void preOrder(int index){
        // 遍历完了 就添加进去
        if(index>=this.length){
            lists.add(new ArrayList<Integer>(list));
            return;
        }
        // 先选择该元素
        list.add(this.arr[index]);
        preOrder(index+1);
        // 再把这个元素删了, 不选择这个元素
        list.remove(list.size()-1);
        preOrder(index+1);
    }
    public List<List<Integer>> subsets(int[] nums) {
        this.length=nums.length;
        this.arr=nums;
        preOrder(0);
        return lists;
    }
}
